#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10000;
namespace ac{
int a[maxn][maxn];
int n,min_num,max_num,path[maxn][maxn];//path数组记录最优解的路径
void initRandomize(int arr[], int n, int min, int max)
{
    int i = 0;
    srand(time(0));  						// 设置种子,并生成伪随机序列
    for(i = 0; i < n; ++i)
        arr[i] = rand() % (max - min + 1) + min; // 得到从[min, max]之间的随机数
}
//生成随机数塔
void intit(){
    for(int i=0;i<n;i++){
        initRandomize(a[i],i+1,min_num,max_num);
        for(int j=0;j<=i;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
//寻找最优路径
int find(){
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<=i;j++){
            a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
            if(a[i+1][j]>a[i+1][j+1])path[i][j]=j;
            else path[i][j]=j+1;
        }
    }
    return a[0][0];//最优值
}
//输出路径
void showpath(){
    int index=0;
    cout<<"路径:"<<endl;
    cout<<"(0,0)"<<endl;
    for(int i=0;i<n-1;i++){
        cout<<"->"<<"("<<i+1<<","<<path[i][index]<<")"<<endl;
        index=path[i][index];
    }
}
};
int main()
{
    cout<<"数塔高度:";
    cin>>ac::n;
    cout<<"数塔每个元素的范围:";
    cin>>ac::min_num>>ac::max_num;
    ac::intit();
    cout<<"最大值:"<<ac::find()<<endl;
    ac::showpath();
    getchar();
    getchar();
    return 0;
}
